/*
 * 亲密数_2（4分）
 */

// ALERT: 第一版代码（能得到正确结果。但，运行时间过长，需优化）
/*
#include <stdio.h>


int main() {
	setbuf(stdout, NULL);


	// NOTE: Variable declaration
	int n, factor_i = 1, factor_j = 1;


	// NOTE: Inputs
	printf("Input n:\n");
	scanf("%d", &n);


	// NOTE: Process
	// STEP: 从2开始遍历一直到n，寻找n的亲密数
	for (int i = 2; i < n; ++i) {
		// HINT: 计算外层循环值的真公因数和
		for (int k = 2; k < i; ++k) {
			if (i % k == 0) {
				factor_i += k;
			}
		}

		// HINT: 每一轮遍历内循环的起始数都设定为外循环值+1，这样可以过滤掉重复的比对。比方说2和3比对过了，但外循环到3开始，如果内循环还是从2开始，那么，3和2就是重复的比对。浪费时间。
		for (int j = i + 1; j <= n; ++j) {
			// HINT: 计算内层循环值的真公因数和
			for (int k = 2; k < j; ++k) {
				if (j % k == 0) {
					factor_j += k;
				}
			}

			// HINT: 比对是否是亲密数
			if (factor_i == j && factor_j == i) {
				printf("(%d,%d)\n", i, j);
				break;
			} else {
				factor_j = 1;
			}
		}

		factor_i = 1;
	}



	// NOTE: Outputs


	// NOTE: Ending
	return 0;
}
*/


// ALERT: 网上代码参考（源自：https://blog.csdn.net/xingxing12323/article/details/103403065）
/*
#include <stdio.h>

int LoveNum(int a, int b) {
	int sum = 0, sum1 = 0;

	for (int i = 1; i < a; ++i) {
		if (a % i == 0) {
			sum += i;
		}

		if (b % i == 0 && b != i) {
			sum1 += i;
		}
	}

	if (sum == b && sum1 == a) {
		return 1;
	} else {
		return 0;
	}
}

int main() {
	setbuf(stdout, NULL);

	// NOTE: Variable declaration
	int n;


	// NOTE: Inputs
	printf("Input n:\n");
	scanf("%d", &n);


	// NOTE: Process
	for (int i = 1; i < n; ++i) {
		int sum = 0;

		// HINT: 计算外层循环值的真公因数和
		for (int j = 1; j < i; ++j) {
			if (i % j == 0) {
				sum += j;
			}
		}

		// HINT: 我们认为公因数和必须比外层循环值大
		if (sum > i) {
			if (LoveNum(sum, i)) {
				printf("(%d,%d)\n", i, sum);
				i = sum + 1;
			}
		}
	}


	// NOTE: Outputs


	// NOTE: Ending
	return 0;
}
*/


// REVIEW: 通过对于网上代码参考阅读，我发现，程序的大题框架与我原先的思路一致，只不过在进入内层循环的时候，网上代码多加了一个判断——必须满足外层循环值的真公因数大于外层循环值。
// ALERT: 第二版代码（能得到正确结果，且代码效率有一定提示。但运行时间仍过长。需优化）
/*
#include <stdio.h>


int main() {
	setbuf(stdout, NULL);


	// NOTE: Variable declaration
	int n, factor_i = 1, factor_j = 1;


	// NOTE: Inputs
	printf("Input n:\n");
	scanf("%d", &n);


	// NOTE: Process
	// STEP: 从2开始遍历一直到n，寻找n的亲密数
	for (int i = 2; i < n; ++i) {
		// HINT: 计算外层循环值的真公因数和
		for (int j = 2; j < i; ++j) {
			if (i % j == 0) {
				factor_i += j;
			}
		}

		// ALERT: 我们认为公因数和必须比外层循环值大，才有必要继续循环下去
		if (factor_i > i) {
			// HINT: 每一轮遍历内循环的起始数都设定为外循环值+1，这样可以过滤掉重复的比对。比方说2和3比对过了，但外循环到3开始，如果内循环还是从2开始，那么，3和2就是重复的比对。浪费时间。
			for (int j = i + 1; j <= n; ++j) {
				// HINT: 计算内层循环值的真公因数和
				for (int k = 2; k < j; ++k) {
					if (j % k == 0) {
						factor_j += k;
					}
				}

				// HINT: 比对是否是亲密数
				if (factor_i == j && factor_j == i) {
					printf("(%d,%d)\n", i, j);
					break;
				} else {
					factor_j = 1;
				}
			}
		}


		factor_i = 1;
	}



	// NOTE: Outputs


	// NOTE: Ending
	return 0;
}*/


// REVIEW: 特别鸣谢hacker_wolf对于本代码的优化。本人斗胆转述与总结一下。我们重新理解题意，什么意思叫两个数互为亲密数。就是拿一个数，求其真公因数和是另外一个数。那么，言下之意，如果一个数连求两次真公因数和，若能变回本尊。那么这个数与其真公因数和就是一对亲密数。
#include <stdio.h>


int main() {
	setbuf(stdout, NULL);


	// NOTE: Variable declaration
	int n, factor_i = 1, factor_j = 1;


	// NOTE: Inputs
	printf("Input n:\n");
	scanf("%d", &n);


	// NOTE: Process
	// STEP: 从2开始遍历一直到n，寻找n的亲密数
	for (int i = 2; i < n; ++i) {
		// HINT: 计算i的真公因数和(factor_i)
		for (int j = 2; j < i; ++j) {
			if (i % j == 0) {
				factor_i += j;
			}
		}

		if (factor_i > i) {
			// ALERT: 寻找匹配的亲密数——直接拿最外层循环中i的真公因数和（factor_i）当做目标，再次求解真公因数和（factor_j），看看是否能回到本尊。
			for (int j = 2; j < i; ++j) {
				if (factor_i % j == 0) {
					factor_j += j;
				}
			}
		}

		// HINT: 比对是否是亲密数
		if (i == factor_j) {
			printf("(%d,%d)\n", i, factor_i);
		} else {
			factor_j = 1;
		}

		factor_i = 1;
	}

	// NOTE: Outputs


	// NOTE: Ending
	return 0;
}
